package com.zwj.interview.BFS;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的深度优先遍历(先序、中序、后序)
 * 三种方法遍历
 */
public class 二叉树先序遍历 {


    public List<Integer> preOrder(TreeNode root){
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root!=null){
            return result;
        }
        //先序遍历：先放入根节点  再左节点 又节点
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur=stack.pop();
            result.add(cur.val);
            //再将右子树 左子树放入栈中
            if(root.right!=null){
                stack.push(root.right);
            }
            if(root.left!=null){
                stack.push(root.left);
            }

        }
        return result;
    }



}
